package com.hqq.exercise.array;

/**
 * NumberOf1Between1AndN 从1到n整数中1出现的次数
 * 题目描述:
 * 输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数
 * 样例输入:
 * 12
 * 样例输出:
 * 5
 * Created by heqianqian on 2017/8/19.
 */
public class NumberOf1Between1AndN {

    /**
     * 单纯循环判断1-N中每一个数中1的个数
     */
    public static long numberOf1Between1AndN(long number) {
        long count = 0;
        for (long i = 1; i <= number; i++) {
            count += NumberOf1(i);
        }
        return count;
    }

    /**
     * 优化时间复杂度
     * 思路:
     * 如果N是K位数 依次判断每位数上1的个数 最后求和
     * 例如输入的四位数 那么判断百位出现1的次数
     * 如果百位上的数字大于1 那么出现1的次数等于(高位数字+1)*100
     * 如果百位上的数字等于0 那么出现1的次数等于(高位数字)*100
     * 如果百位上的数字等于1 那么出现1的次数等于(高位数字*100)+低位数字+1
     */
    public static long numberOf1Between1AndNOptimized(long number) {
        long count = 0;
        long i = 1;
        long current, after, before;
        while ((number / i) != 0) {//分别统计每一位上1的个数
            current = (number / i) % 10;//当前位数字
            before = number / (i * 10);//高位数字
            after = number - (number / i) * i;
            if (current > 1) {
                count += (before + 1) * i;
            } else if (current == 0) {
                count = count + before * i;
            } else if (current == 1) {
                count = count + before * i + after + 1;
            }
            i = i * 10;
        }
        return count;
    }

    private static long NumberOf1(long num) {
        long count = 0;
        if (num < 0) {
            num = -num;
        }
        while (num != 0) {
            if (num % 10 == 1) {
                count++;
            }
            num = num / 10;
        }
        return count;
    }
}
